/**
 * 剑指 Offer 56 - II. 数组中数字出现的次数 II
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
 */

// /**
//  * @param {number[]} nums
//  * @return {number}
//  */
// function singleNumber(nums) {
//   const map = new Map();
//   for (let i = 0; i < nums.length; i += 1) {
//     map.set(nums[i], (map.get(nums[i]) || 0) + 1);
//   }
//   for (let i = 0; i < nums.length; i += 1) {
//     if (map.get(nums[i]) === 1) {
//       return nums[i];
//     }
//   }
//   return 0;
// }

/**
 * @param {number[]} nums
 * @return {number}
 */
function singleNumber(nums) {
  const bitLength = 31;
  const bits = new Array(bitLength);
  const bitCounts = new Array(bitLength);
  let bit = 1;
  for (let i = 0; i < bitLength; i += 1, bit <<= 1) {
    bits[i] = bit;
    bitCounts[i] = 0;
  }
  for (let i = 0; i < bitLength; i += 1) {
    bit = bits[i];
    for (let j = 0; j < nums.length; j += 1) {
      if (nums[j] & bit) {
        bitCounts[i] += 1;
      }
    }
  }
  let result = 0;
  for (let i = 0; i < bitLength; i += 1, bit <<= 1) {
    if (bitCounts[i] % 3) {
      result |= bits[i];
    }
  }
  return result;
}

console.log(singleNumber([3, 4, 3, 3]) === 4);
console.log(singleNumber([9, 1, 7, 9, 7, 9, 7]) === 1);
